import java.util.*;

public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 寻找给定两个结点的公共祖先
     * 思路：1.判断root为不为空
     *      2.判断root是否为root
     *      3.递归左树和右树（将根节点左移和右移）
     *      4.判断左，右树有没有找到给定的结点
     *      5.分情况给定返回值
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
        if (leftTree != null && rightTree != null) {
            return root;
        }else if (leftTree != null) {
            return leftTree;
        }else if (rightTree != null) {
            return rightTree;
        }
        return null;
    }

    /**
     * 将一颗二叉树转化为字符串
     * 思路：1.创建 StringBuffer 放入获得的每个字符，最后输出
     *      2.判断root为不为空，不为空添加val值，为空直接返回
     *      3.分情况讨论root的左树和右树
     *       (1)左树不为空，添加”（“，再去递归左树，最后添加”）“
     *       (2)左树为空去判断右树为不为空，
     *          <1>右树为空，直接return返回
     *          <2>右树不为空，添加“（）”
     *       (3)右树为空直接return返回
     *       (4)右树不为空，添加”（“，再去递归右树，最后添加”）“
     *      4.最后利用类型转换将StringBuffer转化为String
     * @param root
     * @return
     */
    public String tree2str(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuffer stringBuffer = new StringBuffer();
        tree2strChild(root,stringBuffer);
        return stringBuffer.toString();
    }
    public void tree2strChild(TreeNode root,StringBuffer sb) {
        if (root == null) {
            return;
        }
        sb.append(root.val);
        if (root.left != null) {
            sb.append("(");
            tree2strChild(root.left,sb);
            sb.append(")");
        }else {
            if (root.right == null) {
                return;
            }else {
                sb.append("()");
            }
        }
        if (root.right != null) {
            sb.append("(");
            tree2strChild(root.right,sb);
            sb.append(")");
        }else {
            return;
        }
    }

    TreeNode pre = null;
    TreeNode cur = null;

    /**
     * 将二叉搜索树转换为双向链表
     * 思路：(利用中序遍历将树转换成一个有序的双向链表)
     *      1.判断树为不为空
     *      2.递归左树去拿到最小值
     *      3.创建两个null结点
     *       (1)pre结点用来遍历树，转换树的左右指向
     *       (2)cur结点指向第一次pre结点指向的结点，用来最后返回链表的头结点
     *      4.递归左树，拿到最小值                     左
     *      5.转变此时结点的left和right的指向          根
     *      6.递归右树                              右
     * @param root
     * @return
     */
    private TreeNode convertNode(TreeNode root) {
        if (root == null) {
            return null;
        }
        convertNode(root.left);
        if (pre == null) {
            pre = root;
            cur = root;
        }else {
            pre.right = root;
            root.left = pre;
            pre = root;
        }
        convertNode(root.right);
        return cur;
    }

    /**
     * 层序遍历树，没有返回值。(利用队列解决)
     * 思路：1.判断树的root为不为空
     *      2.利用一个队列和一个辅助结点完成
     *      3.首先将头结点放入队列中
     *      4.进入循环判断队列为不为空，不为空弹出队列第一个元素给辅助结点并且打印。
     *      5.判断辅助结点的左结点为不为空，不为空将辅助结点左边的结点放入队列中，为空进入下次循环
     *      6.判断辅助结点的右结点为不为空，不为空将辅助结点右边的结点放入队列中，为空进入下次循环
     * @param root
     */
    public void levelOrder1(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            System.out.print(top.val+" ");
            if (top.left != null) {
                queue.offer(top.left);
            }
            if (top.right != null) {
                queue.offer(top.right);
            }
        }
    }


    /**
     *层序遍历树，返回到一个二维的list。(利用队列解决)
     *思路：1.判断树的root为不为空
     *     2.利用一个队列和一个辅助结点完成
     *     3.首先将头结点放入队列中
     *     4.进入循环判断队列为不为空，不为空弹出队列第一个元素给辅助结点并且打印。
     *     5.判断辅助结点的左结点为不为空，不为空将辅助结点左边的结点放入队列中，为空进入下次循环
     *     6.判断辅助结点的右结点为不为空，不为空将辅助结点右边的结点放入队列中，为空进入下次循环
     *     7.要放入到二维的list中需要创立一个List<List<Integer>> list 和 List<Integer> integerList
     *     8.在内层加一个while循环，判断队列的大小，当队列的大小不为0时将弹出的值放入到 List<Integer> integerList当中
     *     (外循环执行一次就要放空队列，队列放空的值存入 List<Integer> integerList中)
     *     9.每次外循环执行完一次就将 List<Integer> integerList 放入到 List<List<Integer>> list中
     *     10.最后返回  List<List<Integer>> list
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> integerList = new ArrayList<>();
            while (size != 0) {
                TreeNode top = queue.poll();
                integerList.add(top.val);
                size--;
                if (top.left != null) {
                    queue.offer(top.left);
                }
                if (top.right != null) {
                    queue.offer(top.right);
                }
            }
            list.add(integerList);
        }
        return list;
    }

    /**
     * 判断一棵树是不是完全二叉树
     * 思路：1.建立一个队列
     *      2.判断root是否为空
     *      3.首先将root结点放入队列
     *      4.进入到while循环，判断队列为不为空。
     *      5.创建一个辅助结点cur，将队列的顶部弹出，并用cur接受。
     *      6.判断cur为不为空
     *          (1)为空直接break调出循环
     *          (2)不为空将cur的左，右结点放入到队列中(不管为不为空都放入)
     *      7.出循环后再去建立while循环，条件为：队列不为空(遍历队列)
     *      8.进入到while循环后不断弹出元素，如果弹出的元素不为空直接返回false，否则一直弹出队列元素直到队列为空
     *
     * @param root
     * @return
     */
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur == null) {
                break;
            }else {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        while (!queue.isEmpty()) {
            TreeNode top = queue.poll();
            if (top != null) {
                return false;
            }
        }
        return true;
    }

    /**
     * 判断一颗树是否对称
     * 思路：1.因为要去判断树的左边和右边对不对称，所以需要两个参数 leftTree 和 rightTree
     *      2.两个参数需要重新写一个方法 isSymmetricChild
     *      3.判断root为不为空
     *      4.调用 isSymmetricChild 方法传入root.left,root.right参数，并返回该方法的返回值
     *      5.判断左树和右树的情况
     *          (1)左树不为空 右树为空 返回false，左树为空 右树不为空 返回false
     *          (2)左右树都为空，返回true
     *          (3)左右树不为空，但左右树的值不同返回false
     *      6.递归左树的左和右树的右相不相同，并将返回值用left接受
     *      7.递归左树的右和右树的左相不相同，并将返回值用right接受
     *      8.当left 和 right 都为true时才返回true
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if ((leftTree != null && rightTree == null) || (leftTree == null && rightTree != null)) {
            return false;
        }
        if (leftTree == null && rightTree == null) {
            return true;
        }
        if (leftTree.val != rightTree.val) {
            return false;
        }
        boolean left = isSymmetricChild(leftTree.left,rightTree.right);
        boolean right = isSymmetricChild(leftTree.right,rightTree.left);
        return left && right;
    }


    /**根据先序遍历结果创建二叉树
     * 思路：1.定义一个成员变量i,用来获取字符串中的每个字符
     *      2.额外创建一个 createTree方法
     *      3.在方法 createTree 中定义一个新的结点root 为空
     *      4.判断获取字符串中的字符是否为 '#'
     *          (1)是，将root 指向创建好的新的结点，并且赋值，值为获取到的字符串
     *                 i++，然后去递归，用root的左树接受，
     *                 再去递归，用root的右树接受
     *          (2)否则 直接 i++
     *      5.判断走完，返回root结点。(如果root为空说明此时没走判断，左树为空返回去调用右树，如果右树为空说明
     *      此时该结点已经走完，返回到改结点的上一层结点)
     * @param traversal
     * @return
     */
    public int i = 0;
    public TreeNode recoverFromPreorder(String traversal) {
        TreeNode root = createTree(traversal);
        return root;
    }
    public TreeNode createTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = recoverFromPreorder(str);
            root.right = recoverFromPreorder(str);
        }else {
            i++;
        }
        return root;
    }
}
